The process of categorizing packets into different flows in a network router or switch is called packet classification. For example, when a computer opens a TCP session with a printer on a network, the computer sends traffic or flow through a router to the printer. Likewise, the printer sends traffic or flow back through the router to the computer.
Packets belonging to the same flow obey a pre-defined rule and are processed in a similar manner by the router. For example, packets with the same source and destination Internet protocol (IP) addresses form a flow. Packet classification is needed for services such as firewalls, quality of service (QOS), and services that require the capability to distinguish and isolate traffic into different flows for processing.
The increased demand for speed, capacity and differentiated services has increased the need for high speed, high capacity, and highly selective flow classifiers. Flow classifiers must be able to process packets at a rate of about 10-20 Mpackets/sec. Flow classifiers must also distinguish up to 2M different flows described by Layer 2-4 parameters. Because flow classification is performed on every packet, flow classification is typically performed in hardware and generally requires hardware acceleration.
Flow classifiers include a search engine and a look up table, which is also called a flow table. Every row in the flow table contains a flow key and a corresponding function. The flow classifier extracts a flow descriptor or search key from the packet. The flow classifier compares the search key to flow keys in the flow table. If a match is found, the packet is processed using the corresponding function. If a match is not found, a default function is applied to the packet.
The search key typically includes selected fields of a header of a packet. The search key may also include internal router parameters such as an ingress port number. The search key may be viewed as a bit string having a fixed length that is created by concatenation of selected packet fields and internal router parameters.
Design of a flow classifier requires balancing of memory requirements and search time. The memory consumed by the look up table is preferably minimized while maintaining a desired search time. Consuming less memory usually increases the number of table lookups. Decreasing the number of table lookups usually increases the size of the flow table and the required system memory.